import random
from typing import List

def generate_test_data(size: int, seed: int = None) -> List[int]:
    """
    生成柠檬水找零测试数据
    
    Args:
        size: 数据规模
        seed: 随机种子，用于生成可重现的数据
    
    Returns:
        List[int]: 顾客支付的账单列表
    """
    if seed is not None:
        random.seed(seed)
    
    bills = []
    for _ in range(size):
        # 随机选择 5, 10, 20 美元
        bill = random.choice([5, 10, 20])
        bills.append(bill)
    
    return bills

def generate_edge_cases() -> List[List[int]]:
    """
    生成边界测试用例
    
    Returns:
        List[List[int]]: 边界测试用例列表
    """
    edge_cases = [
        [5],  # 最小情况
        [10], # 无法找零的情况
        [20], # 无法找零的情况
        [5, 5, 5, 10, 20],  # 示例1
        [5, 5, 10, 10, 20], # 示例2
        [5, 5, 10],  # 简单可以找零
        [5, 10, 5],  # 顺序导致无法找零
        [5, 5, 5, 5, 20, 20, 20, 20, 20, 20, 5],  # 复杂情况
    ]
    return edge_cases

def generate_large_test_case(size: int = 10000) -> List[int]:
    """
    生成大规模测试用例
    
    Args:
        size: 测试用例大小
    
    Returns:
        List[int]: 大规模测试用例
    """
    if size <= 0:
        return []
    
    # 确保前面有足够的5美元用于找零
    # 至少30%是5美元，确保有足够找零
    num_5 = max(size // 2, 1)
    num_10 = size // 4
    num_20 = size - num_5 - num_10
    
    bills = [5] * num_5 + [10] * num_10 + [20] * num_20
    
    # 打乱顺序，但确保开始有一些5美元
    if len(bills) > 1:
        # 保证前几个是5美元
        start_fives = min(3, num_5)
        remaining = bills[start_fives:]
        random.shuffle(remaining)
        bills = bills[:start_fives] + remaining
    
    return bills
